﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace Algorithms
{
    public class MinPQ<T> : IPriorityQueue<T>, IEnumerable<T> where T : IComparable<T>
    {
        private readonly static T Root = default(T);
        private List<T> Items = new List<T>();
        private int MaxCapacity;
        private Comparer<T> Comparator;
        private int Size = 0;

        public MinPQ()
            : this(int.MaxValue)
        {

        }

        public MinPQ(int capacity)
            : this(capacity, null)
        {

        }

        public MinPQ(int capacity, Comparer<T> comparator)
        {
            if (capacity < 1)
            {
                MaxCapacity = 1;
            }
            else
            {
                MaxCapacity = capacity;
            }

            Comparator = comparator;

            Items.Add(Root);    // Root is reserved item, no used!
        }

        #region IEnumerable<T> Members

        public IEnumerator<T> GetEnumerator()
        {
            return Items.GetEnumerator();
        }

        #endregion

        #region IEnumerable Members

        IEnumerator IEnumerable.GetEnumerator()
        {
            return Items.GetEnumerator();
        }

        #endregion

        #region IPriorityQueue<T> Members

        public bool IsEmpty
        {
            get
            {
                return Count == 0;
            }
        }

        /// <summary>
        /// Return the number of items on the priority queue.
        /// </summary>
        public int Count
        {
            get
            {
                return Size;
            }
        }

        /// <summary>
        /// Add a new key to the priority queue.
        /// </summary>
        /// <param name="item"></param>
        public void Enqueue(T item)
        {
            // add x, and percolate it up to maintain heap invariant
            Items.Add(item);
            ++Size;
            Swim(Size);

            if (Size > MaxCapacity)
            {
                //remove the minimum value
                Dequeue();
            }

            AssertIsMinHeap();
        }

        /// <summary>
        /// Delete and return the smallest key on the priority queue.
        /// </summary>
        /// <returns></returns>
        public T Dequeue()
        {
            if (IsEmpty)
            {
                throw new InvalidOperationException("Priority queue underflow");
            }

            Exchange(1, Size);
            T min = Items[Size--];
            Sink(1);
            Items.RemoveAt(Size + 1);

            AssertIsMinHeap();

            return min;
        }

        /// <summary>
        /// return the Minumin value
        /// </summary>
        /// <returns></returns>
        public T Peek()
        {
            if (IsEmpty)
            {
                throw new InvalidOperationException("Priority queue underflow");
            }
            return Items[1];
        }

        /// <summary>
        /// Output with Ascending order, only can call one time
        /// </summary>
        /// <returns></returns>
        public IEnumerable<T> PopupByAscending()
        {
            while (Size-- >= 0)
            {
                yield return Dequeue();
            }
        }

        public IEnumerable<T> PopupByDescending()
        {
            Stack<T> stack = new Stack<T>();
            while (Size-- >= 0)
            {
                stack.Push(Dequeue());
            }
            while (stack.Any())
            {
                yield return stack.Pop();
            }
        }


        #endregion

        #region Conditional Debug

        [Conditional("DEBUG")]
        [DebuggerStepThrough]
        private void AssertIsMinHeap()
        {
            Debug.Assert(IsMinHeap(1));
        }

        /// <summary>
        /// is subtree of Items[1..N] rooted at k a min heap?
        /// </summary>
        /// <param name="k"></param>
        /// <returns></returns>
        private bool IsMinHeap(int k)
        {
            if (k > Size)
            {
                return true;
            }

            int left = 2 * k;
            int right = 2 * k + 1;

            if (left <= Size && Greater(k, left))
            {
                return false;
            }
            
            if (right <= Size && Greater(k, right))
            {
                return false;
            }

            return IsMinHeap(left) && IsMinHeap(right);
        }

        #endregion

        #region Helper functions for compares and swaps.

        private void Swim(int k)
        {
            while (2 * k <= Size)
            {
                int j = 2 * k;
                if (j < Size && Greater(j, j + 1))
                {
                    ++j;
                }

                if (!Greater(k, j))
                {
                    break;
                }

                Exchange(k, j);

                k = j;
            }
        }

        private bool Greater(int i, int j)
        {
            if (Comparator == null)
            {
                return ((IComparable<T>)Items[i]).CompareTo(Items[j]) > 0;
            }
            else
            {
                return Comparator.Compare(Items[i], Items[j]) > 0;
            }
        }

        private void Sink(int k)
        {
            while (k > 1 && Greater(k / 2, k))
            {
                Exchange(k, k / 2);
                k = k / 2;
            }
        }

        private void Exchange(int i, int j)
        {
            T swap = Items[i];
            Items[i] = Items[j];
            Items[j] = swap;
        }

        #endregion
    }
}
